Flexible Byzantine Fault Tolerance
Resources
Dahlia Malkhi, Kartik Nayak and Ling Ren
Subjective fault tolerance and synchrony assumption
Pipelined
Protocol
Chained-PBFT-ish
Steady-state-and-view-change
Non-adaptive adversary
Asynchronous finality
Alive-but-corrupt fault
Alive-but-corrupt replicas actively try to disrupt the system from maintaining a safe consensus decision and they might arbitrarily deviate from the protocol for this purpose. However, if they cannot break safety, they will not try to prevent the system from reaching a (safe) decision
Quorums (balanced quorum sizes in Section 4.2)
$ q_r: locking & unlocking
$ q_c: (pre-commit &) commit
$ q_c \ge q_r(because votes for locking can be votes for commit)
Security condition
Safety: $ q_r + q_c - 1 > (Active-but-corrupt failure)
Liveness: $ 1 - q_c \ge (Omission failure)
Fault tolerance for partially synchronous commit
Non BFT model (separation of omission failure and a-b-c failure)
Byzantine failure: 0
Active-but-corrupt failure: less than$ q_r + q_c - 1
Omission failure: less than or equal to$ 1 - q_c
Total failure: less than$ q_r
BFT model
When$ q_r + q_c - 1 \ge 1 - q_c \iff q_r + 2q_c - 2 \ge 0
Total failure ($ y): $ < q_r + q_c - 1
Byzantine failure ($ x):$ \le 1 - q_c
Active-but-corrupt failure: less than$ q_r + 2q_c - 2
When$ q_r + 2q_c - 2 < 0
Total failure ($ y): $ \le 1 - q_c
Byzantine failure ($ x): $ < q_r + q_c - 1
Omission failure: less than$ 2 - q_r - 2q_c
$ y = f(x)mappings
$ y \ge x -- (0)
$ y < q_r - x-- (1)
$ y \le x - q_r-- (2)
$ q_c \ge q_r \iff 1 - x \ge q_r \iff x \le 1 - q_r -- (3)
(0) and (1) intersects at$ (q_r/2, q_r/2)
(1) and (2) intersects at$ (q_r, 0)
Figure with comparision to CBC (optimal "n/2 + t/2" oracle)
https://gyazo.com/262af8aeced7d0c35412bfcc2afd9771
Synchronous commit
Equivocation fault threshold: less than$ q_r
@Recolor: she256 Annual Conference 2019
https://gyazo.com/62b3d51bf7fe7d7ddd0eb640941bec98
https://gyazo.com/1d393f0f799f6a3e95b909d2bf483735
https://gyazo.com/668384474e73b0f52c3e4c98b99e374c
https://gyazo.com/db19b59b1cf8eb072feb780ec02ebb56
Related works
Shengyun Liu, Paolo Viotti, Christian Cachin, Vivien Quéma, Marko Vukolić
Sync + Async (with coin flipping)
Federated Byzantine Agreement
DAVID MAZIERES (Stellar Development Foundation)
Minjeong Kim (KAIST), Yujin Kwon (KAIST), Yongdae Kim (KAIST)